public class 通配符匹配_记忆化搜索和dp版 {
    public boolean isMatch1(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[][] dp = new int[s.length + 1][p.length + 1];// (0 代表没访问过) (1 代表可以) (2 代表不可)
        return dfs(s,p,0,0,dp);
    }

    // 递归
    private boolean dfs(char[] s, char[] p, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j] == 1;
        }
        boolean ans;
        // i 到底了
        if (i == s.length) {
            // j 也到底了, 肯定是匹配成功了
            if (j == p.length) {
                ans = true;
            } else {
                // i 已经到底了, 但是 j 没有到底, j 位置必须是 * 才可以匹配空字符, 会怎么样交给后面告诉我
                ans = p[j] == '*' && dfs(s,p,i,j + 1,dp);
            }
        } else if (j == p.length) {
            // i 没有到底, 当时 j 到底了, 肯定是匹配失败
            ans = false;
        } else {
            // 如果两个都没有到底
            // 1. 这个位置是 * 字符
            if (p[j] == '*') {
                // * 直接作为空字符串, 跳过 j 字符
                // * 和 i 位置的字符进行匹配, 跳过 i 字符
                ans = dfs(s,p,i,j + 1,dp) || dfs(s,p,i + 1,j,dp);
            } else {
                // 2. 不为 *
                // 想要匹配成功必须要两个相等或者有 ? 匹配任何字符, 会怎么样后面告诉我
                ans = (p[j] == '?' || p[j] == s[i]) && dfs(s,p,i + 1,j + 1,dp);
            }
        }
        dp[i][j] = ans == false ? 2 : 1;
        return ans;
    }
    // dp 版本
    public boolean isMatch(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int n = s.length;
        int m = p.length;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[n][m] = true;
        for (int j = p.length - 1; j >= 0; j--) {
            dp[n][j] = p[j] == '*' && dp[n][j + 1];
        }
        for (int i = s.length - 1; i >= 0; i--) {
            for (int j = p.length - 1; j >= 0; j--) {
                if (p[j] == '*') {
                    dp[i][j] = dp[i][j + 1] || dp[i + 1][j];
                } else {
                    dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }


}
